package sword.offer;

/**
 * 我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class FortyNine {
    /**
     * 动态规划方法
     * 定义dp数组的含义： dp[n] 表示从小到大的第n个丑数
     * 找出状态转移方程： dp[n] = min(dp[p1]*2,dp[p2]*3,dp[p3]*5) 其中pi从1开始
     * 初始化起始值： dp[1] = 1;
     *
     * 不过说实话 这个规律还是挺难找的
     * */
    class Solution {
        public int nthUglyNumber(int n) {
            int[] dp = new int[n+1];
            dp[1] = 1;
            int p1 = 1, p2 = 1, p3 = 1;

            for (int i = 2; i <= n; i++) {
                int num1 = dp[p1] * 2, num2 = dp[p2] * 3, num3 = dp[p3] * 5;
                dp[i] = Math.min(num1, Math.min(num2, num3));
                if(dp[i] == num1){
                    p1++;
                }
                if(dp[i] == num2){
                    p2++;
                }
                if(dp[i] == num3){
                    p3++;
                }
            }
            return dp[n];
        }
    }
}
